1. Field of the Invention
This invention relates to the field of serial data decoding. More particularly, this invention relates to the field of the decoding of serial data composed of interleaved variable length codes and fixed length codes.
2. Description of the Prior Art
It is known to provide data encoding techniques which generate serial data in the form of interleaved variable length codes and fixed length codes. An example of such an encoding technique is that proposed by the Joint Photographic Experts Group (JPEG) and currently under review by the International Standards Organisation.
The JPEG standard is intended for the compression of image data in computer systems. The image data is transformed into the spatial frequency domain by discrete cosine transformation. The ac spatial components have a distinctly different character to the dc spatial components. The ac spatial components are subject to runlength coding to exploit the long runs of zero values in this data. The dc spatial components do not show this characteristic.
The JPEG standard proposes the use of code words with the following syntax for the ac data, i.e. EQU [RUNLENGTH, SIZE], [AMPLITUDE]
In this case RUNLENGTH is the number of zeros preceding a non-zero value. SIZE is the number of bits that will be needed to represent the non-zero value. AMPLITUDE is the non-zero value and has a bit length equal to that specified by SIZE.
Consider the following data stream of image data, EQU . . . 0,0,0,7,0,0,0,0,0,0,11,0,0,0, . . .
The middle portion, comprising six zeros followed by a non-zero value of 11, would be encoded with the value of RUNLENGTH=6. The non-zero value of 11 will require four bits to represent it, and so SIZE=4. The value, of AMPLITUDE is 11, or 1011 in binary. Thus, the sequence 0,0,0,0,0,0,11 is encoded as [6,4], [11].
The JPEG standard proposes the use of code words with the following syntax for the dc data, i.e. EQU [SIZE], [AMPLITUDE]
Each data value is encoded separately with SIZE being equal to the number of bits needed to represent the value and AMPLITUDE being the value itself. A dc data value of 5 would require three bits to represent and so SIZE=3. AMPLITUDE would then equal 5 or 101 in binary.
Having being coded from its raw state into either [RUNLENGTH, SIZE], [AMPLITUDE] or [SIZE], [AMPLITUDE] word pairs, the first word of each word pair is then subject to Huffman coding to exploit the fact that certain word are more common than others. Frequently occurring words are given short Huffman codes, whereas infrequently occurring words are given longer codes. Huffman coding is of the type of coding in which no valid code is a prefix of any longer valid code.
Whilst the JPEG standard gives good compression it does raise problems when decoding the compressed data. As the Huffman codes have differing lengths, it is not possible for a decoder working its way through the serial data stream to know how many bits will make up the next Huffman code. Huffman codes are of the type in which no code is a prefix of a longer code, but even so each new bit of serial data read may or may not be the final bit of a complete valid Huffman code. The Huffman codes are variable length codes as seen by the decoder.
This problem is not so great with the [AMPLITUDE] words. Whilst these words do have differing numbers of bits, their length is specified in the SIZE value of the preceding word in each word pair. Thus, the decoder can read the value of SIZE from the preceding word and known how many bits make up the [AMPLITUDE] word. The [AMPLITUDE] words are fixed length codes as seen by the decoder.
The problems of coping with this serial data stream comprising interleaved variable length codes and fixed length codes are not too great in the non-real time image display systems of the computers for which the JPEG standard is primarily intended. In a computer system the serial data stream can be read into memory and then scanned to identify valid variable length Huffman codes as a separate, non-synchronous operation.
However, problems do arise if you try to use the JPEG standard type data stream in real time systems such as video systems. In these circumstances the video system must cope with a continuous stream of encoded image data which has to be decoded on a real time basis with as little delay as possible.
It is an object of the invention to provide a serial data decoder capable of the high speed decoding of variable length code words.